home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Environments / Small Eiffel 0.4.8 / lib_std / link_list.e < prev    next >
Encoding:
Text File  |  1997-04-13  |  2.6 KB  |  141 lines  |  [TEXT/ttxt]
  1. -- Part of SmallEiffel -- Read DISCLAIMER file -- Copyright (C) 
  2. -- Dominique COLNET and Suzanne COLLIN -- colnet@loria.fr
  3. --
  4. class LINK_LIST[E]
  5.    -- 
  6.    -- One way linked list with internal automatic memorization of
  7.    -- the last access.
  8.    --
  9.  
  10. inherit LINKED_COLLECTION[E];
  11.  
  12. creation
  13.    make, from_collection
  14.  
  15. feature
  16.  
  17. feature -- Creation and Modification :
  18.    
  19.    make is
  20.       -- Make an empty list;
  21.       do
  22.      if first_link /= Void then
  23.         first_link.free;
  24.      end;
  25.      first_link := Void;
  26.      upper := 0;
  27.      last_link := Void;
  28.      mem_idx := 0;
  29.      mem_lnk := Void;
  30.       ensure
  31.      count = 0
  32.       end;
  33.  
  34. feature -- Implementation of deferred :
  35.  
  36.    add_first(element: like item) is
  37.       do
  38.      if first_link = Void then
  39.         !!first_link.make(element,Void);
  40.         upper := 1;
  41.         last_link := first_link;
  42.         mem_idx := 1;
  43.         mem_lnk := first_link;
  44.      else 
  45.         !!first_link.make(element,first_link);
  46.         upper := upper + 1;
  47.         mem_idx := mem_idx + 1;
  48.      end;
  49.       end;
  50.  
  51.    add_last(element: like item) is
  52.       local
  53.      lnk: like first_link;
  54.       do
  55.      if first_link = Void then
  56.         !!first_link.make(element,Void);
  57.         upper := 1;
  58.         last_link := first_link;
  59.         mem_idx := 1;
  60.         mem_lnk := first_link;
  61.      else
  62.         !!lnk.make(element,Void);
  63.         last_link.set_next(lnk);
  64.         upper := upper + 1;
  65.         last_link := lnk;
  66.      end;
  67.       end;
  68.    
  69.    add(element: like item; index: INTEGER) is
  70.       local
  71.      link: like first_link;
  72.       do
  73.      if index = 1 then
  74.         add_first(element);
  75.      elseif index = upper + 1 then
  76.         add_last(element);
  77.      else
  78.         if (index - 1) /= mem_idx then
  79.            go_item(index - 1);
  80.         end;
  81.         !!link.make(element,mem_lnk.next);
  82.         mem_lnk.set_next(link);
  83.         upper := upper + 1;
  84.      end;
  85.       end;
  86.  
  87.    remove_first is
  88.       local
  89.      mem: MEMORY;
  90.       do
  91.      if upper = 1 then
  92.         make;
  93.      else
  94.         mem_lnk := first_link;
  95.         first_link := first_link.next;
  96.         mem.free(mem_lnk.to_pointer);
  97.         mem_lnk := first_link;
  98.         mem_idx := 1;
  99.         upper := upper - 1;
  100.      end;
  101.       end;
  102.  
  103.    remove(index: INTEGER) is
  104.       local
  105.      mem: MEMORY;
  106.      link: like first_link;
  107.       do
  108.      if index = 1 then
  109.         remove_first;
  110.      elseif index = upper then
  111.         remove_last;
  112.      else
  113.         if (index - 1) /= mem_idx then
  114.            go_item(index - 1);
  115.         end;
  116.         link := mem_lnk.next;
  117.         mem_lnk.set_next(link.next);
  118.         mem.free(link.to_pointer);
  119.         upper := upper - 1;
  120.      end;
  121.       end;
  122.  
  123. feature {NONE}
  124.  
  125.    go_item(i: INTEGER) is
  126.       do
  127.      if mem_idx > i then
  128.         mem_idx := 1;
  129.         mem_lnk := first_link;
  130.      end;
  131.      from
  132.      until
  133.         i = mem_idx
  134.      loop
  135.         mem_lnk := mem_lnk.next;
  136.         mem_idx := mem_idx + 1;
  137.      end;
  138.       end;
  139.  
  140. end -- LINK_LIST[E]
  141.